//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
#include <algorithm>
using namespace std;
int dfs(int target, vector<int> c){
    if (target==0)return 0;

    int minCoins = INT_MAX;
    for (int num:c){
        if (target-num<0)continue;
        int subMinCounts = dfs(target-num, c);
        if (subMinCounts==-1)continue;
        minCoins = min(minCoins, subMinCounts+1);
    }
    return minCoins == INT_MAX ? -1 : minCoins;

}
int coinChange(vector<int>& coins, int amount) {
    int res = dfs(amount, coins);
     res = res==INT_MAX?-1:res;
    return res;
}

//记忆化搜索
// 回溯 + 记忆化搜索
// 计算返回凑成总金额 target 需要的最少硬币数
int dfs1(int target, vector<int>& coins, vector<int>& memo) {
    if (target == 0) return 0;
    if (memo[target] != INT_MAX) return memo[target];

    int minCoins = INT_MAX;
    for (int i = 0; i < coins.size(); i++) {
        if (target - coins[i] < 0) continue;
        int subMinCoins = dfs1(target - coins[i], coins, memo);
        if (subMinCoins == -1) continue;
        minCoins = min(minCoins, subMinCoins + 1);
    }

    memo[target] = minCoins == INT_MAX ? -1 : minCoins;
    return memo[target];
}

int coinChange1(vector<int>& coins, int amount) {
    vector<int> memo(amount + 1, INT_MAX);
    return dfs1(amount, coins, memo);
}

//动态规划
int coinChange2(vector<int>& coins, int amount) {
    if (amount < 0) return -1;
    if (amount == 0) return 0;
    vector<int> dp(amount+1, INT_MAX);
    //初始化矩阵
    dp[0]=0;

    for (int target = 1; target <= amount; ++target) {
        for (int c:coins){
            if(target-c>=0 && dp[target-c]!=INT_MAX)
                dp[target] = min(dp[target], dp[target-c]+1);
        }
    }
    return dp[amount]==INT_MAX?-1:dp[amount];

}

//基于完全背包的动态规划
//转化为完全背包问题：
//从coins 列表中可重复选择最少数量的硬币，使得他们的总金额为amount
int coinChange3(vector<int>& coins, int amount) {
    // 1. 状态定义：dp[c] 表示凑齐总金额为 c 的时候需要的最小硬币数
    vector<int> dp(amount + 1, amount + 1);

    // 2. 凑齐总金额为 0 的时候需要的最小硬币数就是不取硬币
    dp[0] = 0;

    //状态转移
    for (int i = 0; i <coins.size() ; ++i) {
        for (int a = coins[i]; a<=amount; ++a) {
            dp[a] = min(dp[a], 1+dp[a-coins[i]]);
        }
    }
    return dp[amount]==amount + 1?-1:dp[amount];

}
